#include<bits/stdc++.h>
using namespace std;
struct Trie
{
    unordered_map<char,Trie*> children;
    priority_queue<string,vector<string>> q;
};
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        Trie* root=new Trie();
        for(const string& s:products)
        {
            Trie* cur=root;
            for(char ch:s)
            {
                if(!cur->children.count(ch)) cur->children[ch]=new Trie();
                cur=cur->children[ch];
                cur->q.push(s);
                if(cur->q.size()>3) cur->q.pop();
            }
        }
        vector<vector<string>> ret;
        bool flag=false;
        Trie* cur=root;
        for(char ch:searchWord)
        {
            if(flag||!cur->children.count(ch))
            {
                flag=true;
                ret.emplace_back();
            }
            else
            {
                vector<string> vec;
                cur=cur->children[ch];
                while(!cur->q.empty())
                {
                    vec.push_back(cur->q.top());
                    cur->q.pop();
                }
                reverse(vec.begin(),vec.end());
                ret.push_back(vec);
            }
        }
        return ret;
    }
};